#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class Solution
{
public:
    // dp(i,s) 从第0到第i个元素挑选出一些元素使得和为s
    // d(i, s) = d(i-1, s){不取nums[i]} || d(i-1, s-nums[i]){取nums[i]}
    bool canPartition(vector<int> &nums)
    {
        int sum = 0;
        for (int &it : nums)
        {
            sum += it;
        };
        if (sum % 2 == 1 || nums.size() <= 1)
            return false;
        vector<vector<bool>> dp(nums.size(), vector<bool>((sum >> 1) + 1, false));
        if (nums[0] <= (sum >> 1))
            dp[0][nums[0]] = true;
        for (int i = 1; i < nums.size(); ++i)
        {
            for (int s = 0; s < sum / 2 + 1; ++s)
            {
                if (dp[i - 1][s] == true)
                    dp[i][s] = true;
                else if (s < nums[i])
                    continue;
                else
                    dp[i][s] = dp[i - 1][s - nums[i]];
            }
        }
        return dp[nums.size() - 1][sum >> 1];
    }
};